package beautiful.sort;

/**
 * @author: LWQ
 * @description: TODO
 * @date: 2022-2-6 23:01
 * @version: 1.0
 */
public class InsertionSort {
    public static void main(String[] args) {
        int arr[] = {1,2,5,4,3,7,6,8};
        insertionSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void insertionSort(int[] arr) {
        if (arr.length <= 1) return;
        for (int i = 0; i < arr.length; i++) {
            int value = arr[i];
            int j = i-1;
            // 循环移动后面数据
            for (; j >= 0; --j) {// 和有序区里面的比较交换
                if(arr[j] > value){
                    arr[j + 1] = arr[j];
                }else {
                    break;
                }
            }
            // 搬运完了，直接插入数据
            arr[j + 1] = value;
        }
    }
}
